package LeetCode;

//【动态规划】  https://leetcode-cn.com/problems/ones-and-zeroes/
public class LC474 {
    public int findMaxForm(String[] strs, int m, int n) {
        // dp[i][j]表示i个0和j个1限制下的最多数量
        if(strs.length==0) return 0;
        int[][] dp = new int[m + 1][n + 1];
        for(String s :strs) {
            //状态转移方程：dp[i][j] = Math.max(dp[i][j],1+dp[i-numZero][j-numOne])
            int zeros  = 0,ones = 0;//统计字符串中一和零的数量。
            for(char c:s.toCharArray()) {
                if (c == '0') {
                    zeros++;
                }else {
                    ones++;
                }
            }
            //这种题做多了之后就知道就是这个套路。
            for (int i = m; i >=zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = Math.max(dp[i][j], 1+dp[i-zeros][j-ones]);
                }
            }
        }
        return dp[m][n];
    }
}
